package test;

import java.util.Random;

public class SkipList<T> {

    /**
     * 跳表的头尾
     */
    public Node<T> head,tail;

    /**
     * 跳表所含的关键字的个数
     */
    public int size;

    /**跳表的层数
     *
     */
    public int level;

    /**随机数发生器
     *
     */
    public Random random;

    /**
     * 向上一层的概率
     */
    public static final double PROBABILITY=0.5;

    /**
     * 跳表的构造函数
     */
    public SkipList(){
        //初始化头尾节点及两者的关系
        head=new Node<>(Node.HEAD_KEY, null);
        tail=new Node<>(Node.TAIL_KEY, null);
        head.next=tail;
        tail.pre=head;
        //初始化大小，层，随机
        size=0;
        level=0;
        random=new Random();
    }

    public void printSkipList(){
        System.out.println("跳表打印开始，总层数为"+level+",节点个数为"+size);
        Node<T> first=head;
        Node<T> p=first;
        int currentLevel=level;
        while(first!=null){
            //循环first这一层
            System.out.print("打印第"+currentLevel+"层:  ");
            p=first;
            while (p!=null) {
                System.out.print(p+"  ");
                p=p.next;
            }
            first=first.down;
            currentLevel--;
            System.out.println();
        }
        System.out.println();
    }

    /**1. 如果put的key，在跳表中不存在，则在跳表中加入，并由random产生的随机数决定生成几层，返回一个null
     * 2. 如果put的key存在，则在跳表中对应的node修改它的value，并返回过去的value
     * @param key
     * @param value
     * @return
     */
    public T put(int key,T value){
        //首先得到跳表最底层中，最接近这个key的node
        Node<T> p=findNearestNode(key);
        if(p.key==key){
            //如果跳表中有这个key，则返回最底层中，对应这个key的node
            //在跳表中，只有最底层的node才有真正的value，只需修改最底层的value就行了
            T old=p.value;
            p.value=value;
            return old;
        }

        //如果跳表中，没有这个key，那么p就是最底层中，小于这个key，并且最接近这个key的node
        //q为新建的最底层的node
        Node<T> q=new Node<>(key, value);
        //在最底层，p的后面插入q
        insertNodeHorizontally(p, q);

        //当前level（要与总层数Level进行比较）
        int currentLevel=0;

        //PROBABILITY为进入下一层的可能性，nextDouble()返回[0,1)
        //小于PROBABILITY，说明可能性到达（比如说假设为0.7，小于它的概率就是0.7），进入循环，加入上层节点
        while (random.nextDouble()<PROBABILITY) {
            //最底层为0，到这里currentlevel为当前指针所在的层，被插入的镜像变量在currentlevel+1层
            //所以currentLevel=level时，要在level+1层插入，就要加入一层
            if(currentLevel>=level){
                addEmptyLevel();
            }
            //找到q的左边(也就是<=p)第一个能够up的节点，并上浮，赋予p
            while (p.up==null) {
                p=p.pre;
            }
            p=p.up;

            //创建q的镜像变量z，只有key，没有value，插入在现在的p的后面
            Node<T> z=new Node<>(key, null);
            insertNodeHorizontally(p, z);

            //设置z与q的上下关系
            z.down=q;
            q.up=z;

            //指针上浮
            q=z;
            currentLevel++;

        }
        //插入完毕后，size扩大，返回null
        size++;
        return null;
    }


    /**返回跳表最底层中，最接近这个key的node<br>
     * 如果跳表中有这个key，则返回最底层中，对应这个key的node<br>
     * 如果没有这个key，则返回最底层中，小于这个key，并且最接近这个key的node
     * @param key
     * @return
     */
    private Node<T> findNearestNode(int key){
        Node<T> p=head;
        Node<T> next;
        Node<T> down;
        while (true) {
            next=p.next;
            //p先前进到这一层中（一开始在最顶层），p的next>key的位置，然后再考虑向下
            if(next!=null&&next.key<=key){
                p=next;
                continue;
            }
            down=p.down;
            //走到这一步，p在这一层已经无法前进了，就下降一层，在那层进入循环，再往前走
            if(down!=null){
                p=down;
                continue;
            }
            //到这里，说明已经无法再向下（已经到最底层），无法再向前（当前的p<=key,next>key)，最接近key，跳出循环
            break;
        }
        return p;
    }

    /** 在同一层，水平地，在pre的后面，插入节点now
     * @param pre 插入节点前面的节点，应该pre.key小于now.key小于pre.next.key
     * @param now 插入的节点
     */
    private void insertNodeHorizontally(Node<T> pre,Node<T> now){
        //先考虑now
        now.next=pre.next;
        now.pre=pre;
        //再考虑pre的next节点
        pre.next.pre=now;
        //最后考虑pre
        pre.next=now;
    }

    /**
     * 在现在的最顶层之上新加一层，并更新head和tail为新加的一层的head和tail,然后更新总level数（字段level）
     */
    private void addEmptyLevel(){
        Node<T> p1=new Node<T>(Node.HEAD_KEY, null);
        Node<T> p2=new Node<T>(Node.TAIL_KEY, null);
        //设置p1的下右
        p1.next = p2;
        p1.down = head;
        //设置p2的下左
        p2.pre = p1;
        p2.down = tail;
        //设置之前头尾的上
        head.up = p1;
        tail.up = p2;
        //设置现在的头尾
        head=p1;
        tail=p2;
        //更新level
        level++;
    }

    /**根据key，返回最底层对应的node，如果不存在这个key，则返回null
     * @param key
     * @return
     */
    public Node<T> get(int key){
        //返回跳表最底层中，最接近这个key的node
        Node<T> p=findNearestNode(key);
        //如果key相同，返回这个node
        if(p.key==key){
            return p;
        }
        //如果不相同，返回null
        return null;
    }


    /**在跳表中删除这个key对应的所有节点（包括底层节点和镜像节点）<br>
     * 如果确实有这个key，返回这个key对应的value<br>
     * 如果没有这个key，返回null
     * @param key
     * @return
     */
    public T remove(int key){
        //在底层找到对应这个key的节点
        Node<T> p=get(key);
        if(p==null){
            //如果没有这个key，返回null
            return null;
        }

        T oldValue=p.value;
        Node<T> next;
        while (p!=null) {
            next=p.next;
            //在这一行中，将p删除
            //设置p的next和pre的指针
            next.pre=p.pre;
            p.pre.next=next;

            //p上移，继续删除上一行的p
            p=p.up;
        }

        //更新size，返回旧值
        size--;
        return oldValue;
    }

}
class Node<T> {

    /**
     * 在跳表中排序的关键字
     */
    public int key;

    /**
     * 在跳表中存储的值，每个key对应一个value（也可以不放value，这样就相当于从treemap变成treeset）
     * 注意：在跳表中，只有最底层的node才有真正的value，其它层的node的value都为null，查找时会到最底层得到value
     */
    public T value;

    /**
     * 左右节点
     */
    public Node<T> pre,next;

    /**上下节点
     *
     */
    public Node<T> up,down;

    /**
     * 头结点被设置成int的min
     */
    public static int HEAD_KEY=Integer.MIN_VALUE;

    /**尾节点被设置成int的max
     *
     */
    public static int TAIL_KEY=Integer.MAX_VALUE;

    /**Node的构造函数
     * @param key  在跳表中排序的关键字
     * @param value  在跳表中存储的值，每个key对应一个value
     */
    public Node(int key, T value) {
        this.key = key;
        this.value = value;
    }

    public int getKey() {
        return key;
    }

    public void setKey(int key) {
        this.key = key;
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node [key=" + key + ", value=" + value + "]";
    }

}